package leetcode.meituan.p1;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author caojie
 * @version 1.0
 * @Description  * https://codefun2000.com/p/P1287
 * @date 2023/8/18 11:31
 */
public class Test1 {
    void test1(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            String[] s = scanner.nextLine().split(" ");
            String max = "";
            String str = s[0];
            String reg = s[1];
            boolean flag = false;
            for (int j = 0; j < str.length(); j++) {
                if(reg.charAt(0) > str.charAt(j)){
                    flag = true;
                    if(j == 0){
                        max = reg+str;
                        break;
                    }else{
                        String a = str.substring(0, j );
                        String b = str.substring(j, str.length());
                        max = a + reg + b;
                        break;
                    }
                }
            }
            if(!flag){
                max = str + reg;
            }
            System.out.println(max);
        }

        int c = 1;
    }

//    3
//    9
//    0 0 1 0 0 1 0 0 1
//    0 1 1 2 3 3 4 5 5
//    0 0 1 1 1 2 2 2 3
//    6
//    1 1 0 1 1 0
//    4
//    1 0 0 0

//    5 4 4 4 3 5 3 2 6
//    3 2 3 2 1 4
//    0 3 2 1
//    对于某个位置的0，他只打得过左边的1和右边的0
//    对于某个位置的1，他只打得过左边的0和右边的1
//    南派北派武林大会开始了。本次攻擂赛有
//    n 名武者参加，其中按顺序第
//    i 名武者获得战斗力属性为
//    i 。每名武者分来自南派或者北派。如果不同派系的武者在擂台上相遇，战斗力属性值大的获得胜利，如果同派系的武者在擂台上相遇，强者会相让弱者，战斗力属性值小的会获得胜利。参加战斗的所有武者两两都会进行一场决斗，请你计算出每名武者获胜的次数。
    void test2(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            if(i == 0){
                scanner.nextLine();
            }
            int p = scanner.nextInt();
            scanner.nextLine();
            String[] w = scanner.nextLine().split(" ");
            int[] zero = new int[p];
            int[] one = new int[p];
            if(w[0].charAt(0) == '0'){
                zero[0] = 1;
            }else{
                one[0] = 1;
            }
//            0 0 1 0 0 1 0 0 1
            for (int j = 1; j < p; j++) {
                if(w[j].charAt(0) == '0'){
                    zero[j] = zero[j-1]+1;
                    one[j] = one[j-1];
                }else{
                    zero[j] = zero[j-1];
                    one[j] = one[j-1] + 1;
                }
            }

            int res = 0;
            for (int j = 0; j < p; j++) {
                if(j==0){
                    if(w[j].charAt(0) == '0'){
                        res=  zero[p-1]-zero[0];
                    }else{
                        res =  one[p-1]-one[0];
                    }
                }else{
                    if(w[j].charAt(0) == '0'){
                        res=one[j-1] + zero[p-1] - zero[j];
                    }else{
                        res = zero[j-1] + one[p-1] -one[j];
                    }
                }
                System.out.print(res+" ");
            }
            System.out.println("");
        }
    }
    public static void main(String[] args) {
        Test1 test1 = new Test1();
        test1.test2();
    }
}
